package com.rew.navi.Dijkstra;


import com.rew.navi.models.GMap;
import com.rew.navi.models.GNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Dijkstra.
 *
 * Created by HuiWen Ren on 2016/9/2.
 */


public class Dijkstra {


    private static final int INF = 0x3ffffff;

    private int[][] cost; // 邻接矩阵
    private int v; // 顶点个数
    private int[] dis; // 最短距离集
    private boolean[] used; // 标记使用

    private void initDIJ(MapBuilder mapBuilder){

        cost = mapBuilder.mapBuild();
        v = mapBuilder.getNum() - 1; // 暂不考虑终点
        dis = new int[v];
        used = new boolean[v];

        for (int i = 0; i < dis.length; i++){
            dis[i] = INF;
            used[i] = false;
        }

        for (int i = 0; i <= dis.length; i++){
            for (int j = 0; j <= dis.length; j++){
                cost[i][j] = cost[i][j] == -1 ?
                        INF : cost[i][j];
            }
        }
        dis[v - 1] = 0; // 除去开始结点
    }

    public List<GNode> runDijskra(GMap gMap, GNode stPoint, GNode enPoint){
        MapBuilder mapBuilder = new MapBuilder(gMap, stPoint, enPoint);
        List<GNode> ans = new ArrayList<>();
        initDIJ(mapBuilder);
        while (true){
            int k = -1;
            for (int i = 0; i < v; i++){
                if (!used[i] && (k == -1 || dis[i] < dis[k])){
                    k = i;
                }
            }
            if (k == -1){
                break;
            }
            used[k] = true;
            for (int i = 0; i < v; i++){
                if (dis[i] >  dis[k] + cost[k][i]) {
                    dis[i] = dis[k] + cost[k][i];
                    mapBuilder.find(i).parent = mapBuilder.find(k);
                }
                 dis[i] = Math.min(dis[i], dis[k] + cost[k][i]);
            }
        }

        int mdis = INF;
        int cod = 0;
        for (int i = 0; i < cost[v].length; i++){
            if (cost[v][i] < mdis && cost[v][i] != 0){
                mdis = cost[v][i];
                cod = i;
            }
        }

        mapBuilder.find(v).parent = mapBuilder.find(cod);

        GNode tmp = mapBuilder.find(v);
        while (tmp.parent != null){
           ans.add(tmp);
           tmp = tmp.parent;
       }
        return ans;
    }

}
